
#include <iostream>
#include <math.h>
#include <fstream>
#include <sys/time.h>
#include <iomanip>
#include <string.h>


using namespace std;

#define SIGMA_SIZE 256

typedef unsigned long long timestamp_t;

/*
 * returns current timestamp for benchmark
 */
static timestamp_t get_timestamp() {
	struct timeval now;
	gettimeofday(&now , NULL);
	return now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
}

/*
 * 2. phase of suffix array slgorithm.  Sorts Buckets after init.
 */
void bucket_sort(string text , int pos[], int suf[] , bool bucket_start[] , bool bucket_start2[] , int bucket_size[]) {

	int logn = ceil( log(text.size()) / log(2) );

	//Run log n phases
	for (int h=0; h < logn; h++) {
		int l = 0;
		for (unsigned int i=0;i<text.size();i++) {
			if (bucket_start[i]) {
				l = i;
				bucket_size[l] = 0;
			}
			//bucket number
			suf[pos[i]] = l;
		}


		for (unsigned int j=0;j<text.size();j++) {
			if (!bucket_start[j])
				continue;

			unsigned int i = j;
			while((!bucket_start[i] || i==j) && i < text.size()) {

				unsigned int d = pos[i] - pow(2 , h);
				//if new start pos is 'before' word (< 0) skip it
				if (d<0 || d >= text.size()) {
					i++;
					continue;
				}

				//get bucket number
				int k = suf[d];
				//position in bucket
				suf[d] = k + bucket_size[k];
				//increase bucket size
				bucket_size[k]++;
				//mark position as changed
				bucket_start2[suf[d]] = true;
				i++;
			}

			i = j;
			//Look only at current bucket
			while((!bucket_start[i] || i==j) && i < text.size()) {
				unsigned int d = pos[i] - pow(2 , h);
				//Skip word that start 'before' text position 0
				if (d<0 || d >= text.size() || !bucket_start2[suf[d]]) {
					i++;
					continue;
				}

				//get min j | j > suf[d] && (bucket_start[j] || !bucket_start2[j])
				int k = -1;
				for (unsigned int h = suf[d]+1; h<text.size(); h++) {
					if (bucket_start[h] || !bucket_start2[h]) {
						k = h;
						break;
					}
				}
				//End min ...

				for (int l = suf[d]+1; l < k; l++) {
					bucket_start2[l] = false;
				}
				i++;
			}


		}

		//write current bucket starts and pos in array
		for (unsigned int i = 0; i < text.size(); i++) {
			pos[suf[i]] = i;
			bucket_start[i] = bucket_start[i] || bucket_start2[i];
		}

	}
}


/**
 * Initialize sorting for first letter of suffixes for the given text
 */
void init(string text ,int pos[], int suf[] , bool bucket_start[] , bool bucket_start2[] , int bucket_size[]) {
	//Init buckets with -1 (saves first loop in pseudocode)
	int bucket[ SIGMA_SIZE ];
	memset(bucket, -1, sizeof bucket);



	int b;
	for (unsigned int i=0; i < text.size(); i++) {

		//cout << i << " : " <<  text[i] << " - " << (unsigned int)text[i] << endl;
		b = bucket[(unsigned int)text[i]];
		bucket[(unsigned int)text[i]] = i;
		pos[i] = b;
	}

	int c = 0; //Is 1 in pseudocode

	//For each d in Sigma
	for (int d = 0; d < SIGMA_SIZE; d++) {
		int i = bucket[d];
		while (i != -1) {
			int j = pos[i];
			suf[i] = c;
			if (i == bucket[d]) {
				bucket_start[c] = true;
			} else {
				bucket_start[c] = false;
			}
			c++;
			i = j;
		}
	}

	//*********************************************
	bucket_start[text.size()-1] = true;

	for (unsigned int i=0; i<text.size(); i++) {
		pos[suf[i]] = i;
	}


}

/**
 * Checks if a string is a prefix of another string
 */
bool prefix(string prefix , string text) {
	if (prefix.length() >= text.length())
		return false;

	return (std::mismatch(prefix.begin(), prefix.end(), text.begin()).first == prefix.end());
}

/**
 * Search for a given text using the suffix array for this text. (standard binary search) (left boundary)
 */
int search_left(string text , string search , int pos[]) {
	//If first one is already bigger return 0
	if (text.substr(pos[0] , text.size()) > search) {
		return -1;
	}

	//If last one is smaller return abs(X)
	if (text.substr(pos[text.size()-1] , text.size()) < search) {
		return text.size();
	}

	//Else perform binary search for left boundary
	int l = 0;
	int r = text.size()-1;
	while(r-l > 1) {
		int m = ceil((l+r) / 2);
		if (text.substr(pos[m] , text.size()) > search)
			r = m;
		else
			l = m;

	}

	if (prefix(search , text.substr(pos[r] , text.size())))
		return r;
	else
		return -1;
}

/**
 * Search for a given text using the suffix array for this text. (standard binary search) (right boundary)
 */
int search_right(string text , string search , int pos[] , int left_start) {
	//If first one is already bigger return 0
	if (text.substr(pos[0] , text.size()) > search) {
		return -1;
	}

	//If last one is smaller return abs(X)
	if (text.substr(pos[text.size()-1] , text.size()) < search) {
		return text.size();;
	}

	//Else perform binary search for left boundary
	int l = left_start;
	int r = text.size()-1;
	while(r-l > 1) {
		int m = ceil((l+r) / 2);
		if (prefix(search , text.substr(pos[m] , text.size()))) {
			l = m;
		} else {
			r = m;
		}
	}
	//If left border is on position n-1 and right border on position n we won't go into the loop and would return l. Prevent this:
	if (prefix(search , text.substr(pos[r] , text.size())))
		l = r;
	return l;
}


void print_result(int l, int r, int pos[] , int search , double time) {
	int app;
	if (r == -1)
		app = 0;
	else
		app = r - l + 1;



	cout << "Pattern " << search << ": ";
	cout << app << " Appearances; ";
	if (app > 0) {
		cout << "lex. smallest: " <<  pos[l] << "; ";
		cout << "lex. biggest: " <<  pos[r] << "; ";
	}
	cout << "time: " << time  << " s; ";
	cout << endl;

}

/**
 * Wrapper for binary searches
 */
void search(string search , int pos[] , string text , int num) {

	//start timer
	timestamp_t t0 = get_timestamp();

	//start bin. search
	int l = search_left(text , search , pos);
	int r;
	if (l == -1 || l == text.size()) {
		r = -1;
	} else {
		r = search_right(text , search , pos , l);
	}

	//end timer + compute running time
	timestamp_t t1 = get_timestamp();

	double s = (t1-t0) / 1000000.0L;

	print_result(l , r , pos , num , s);

}

int main(int argc, char *argv[]) {

	// Path of the txt file
	string text_str;
	// Path of the pattern file
	string pattern_str;
	if (argc > 2) {
		text_str = argv[1];
		pattern_str = argv[2];

	} else {
		text_str = "./input/text6.txt";
		pattern_str = "./input/text6.pat";
	}

	const char *text_file = text_str.c_str();
	const char *pattern_file = pattern_str.c_str();

	// Getting the text from the file
	string text;

	std::ifstream textfile(text_file);

	if (textfile.is_open()) {

	    getline(textfile , text , '$');
	    text += "$";
		textfile.close();
	}
	else {
		std::cout << "[Error] Unable to open file "<< argv[1] << std::endl;
		return 0;
	}


	//text = "a\na\na\na\na\na\na\na\na\na\na\na\na\na\na\na\na\na\n$";

	//std::cout << "============= TEXT START =============" <<std::endl;
	//std::cout << text <<std::endl;
	//std::cout << "============= TEXT END =============" <<std::endl;



	int pos[text.size()];
	int suf[text.size()];

	bool bucket_start[text.size()];
	memset(bucket_start, false, sizeof bucket_start);
	bool bucket_start2[text.size()];
	memset(bucket_start2, false, sizeof bucket_start2);

	int bucket_size[text.size()];
	memset(bucket_size, 0, sizeof bucket_size);

	//Start timer for Benchmark
	timestamp_t t0 = get_timestamp();



	init(text , pos , suf , bucket_start , bucket_start2 , bucket_size);

	bucket_sort(text , pos , suf , bucket_start , bucket_start2 , bucket_size);

	//prevent scientific notation for small numbers
	cout << fixed << showpoint;
	cout << setprecision(8);
	//Stop timer for Benchmark
	timestamp_t t1 = get_timestamp();

	//Get seconds
	double s = (t1-t0) / 1000000.0L;

	//print runtime
	cout << "Suffix-Array : " << s << " s" << endl;


	// Getting the patterns from the file
	string pattern;

	std::ifstream patternfile(pattern_file);
	int pattern_num = 1;
	if (patternfile.is_open()) {

		//flag so the first letter of the first character will not be deleted
		bool flag = false;

		while (!patternfile.eof())
		{
			getline(patternfile , pattern , '$');
			if(flag){ //make sure the first patterns first character will not be deleted
				pattern.erase(0,1); //erase '\n' from string pattern
			}
			else{
				flag = true;
			}
			if (pattern.size() > 0){ //make sure no empty patterns are used
				search(pattern , pos , text , pattern_num++);
			}
		}
	    patternfile.close();
	}
	else {
		std::cout << "[Error] Unable to open file "<< argv[2] << std::endl;
		return 0;
	}


//prints pos array
/*
	cout << "POS: ";
	for (unsigned int i=0 ; i<text.size();i++) {
		cout << pos[i] << " ";
	}
	cout << endl;
*/
/*
	cout << text.substr(8754 , 400) << endl;
	cout << endl;
	cout << text.substr(7007 , 400) << endl;
	cout << endl;
	cout << text.substr(4187 , 400) << endl;
*/

	//prints bucket_start array
/*
	cout << "Bucket Start: ";
	for (int i=0 ; i<text.size();i++) {
		cout << bucket_start[i] << " ";
	}
	cout << endl;
*/
	return 0;
}
